import math
import random
from collections import deque
from ModelLoader import *

class Vertices():

    def __init__(self):
        # Counters for ID nums
        self.vertCount = 0
        self.polyCount = 0
        # Coords to ID and back
        self.coordsId = {}
        self.idCoords = {}
        # Vert to list of polyIDs
        self.vertPolys = {}
        # PolyID to list of vert triangles
        self.polyVerts = {}
        # Edges
        self.verts = {}
        # Rendering: true polys & normals
        self.polys = []
        # Redering: vertices
        self.vertList = []
        # Rendering: edges
        self.edList = []
        # Display List
        self.display = True
        # Recalc normals
        self.modif = False
        # Auto-detect polys
        self.smart = True
        # Set normals away from 0,0,0
        self.center = True

    def solveNorm(self, p):
        qx = p[1][0] - p[0][0]
        qy = p[1][1] - p[0][1]
        qz = p[1][2] - p[0][2]
        px = p[2][0] - p[0][0]
        py = p[2][1] - p[0][1]
        pz = p[2][2] - p[0][2]
        nx = py*qz - pz*qy
        ny = pz*qx - px*qz
        nz = px*qy - py*qx
        sn = math.sqrt(math.pow(nx,2)+math.pow(ny,2)+math.pow(nz,2))
        if sn != 0:
            nx = float(nx)/sn
            ny = float(ny)/sn
            nz = float(nz)/sn
        else:
            nx = 0
            ny = 0
            nz = 0
        ax = (float(p[0][0]+p[1][0]+p[2][0])/3)
        ay = (float(p[0][1]+p[1][1]+p[2][1])/3)
        az = (float(p[0][2]+p[1][2]+p[2][2])/3)
        sa = math.sqrt(math.pow(ax,2)+math.pow(ay,2)+math.pow(az,2))
        ax = float(ax)/sa
        ay = float(ay)/sa
        az = float(az)/sa
        mx = ax*nx
        my = ay*ny
        mz = az*nz
        if (mx + my + mz) > (-1*mx + -1*my + -1*mz) or not self.center:
            return (nx,ny,nz)
        else:
            return (-1*nx,-1*ny,-1*nz)

    
    def addVertex(self,vertex):
        if vertex in self.coordsId:
            pass
        else:
            id = self.vertCount
            self.vertCount += 1
            self.coordsId[vertex] = id
            self.idCoords[id] = vertex
            self.verts[id] = []
            self.vertPolys[id] = []
            self.vertList.append(vertex)
        self.display = True

    def addEdge(self,start,end):
        if start in self.coordsId:
            startID = self.coordsId[start]
        else:
            startID = self.vertCount
            self.vertCount += 1
            self.coordsId[start] = startID
            self.idCoords[startID] = start
            self.verts[startID] = []
            self.vertPolys[startID] = []
            self.vertList.append(start)

        if end in self.coordsId:
            endID = self.coordsId[end]
        else:
            endID = self.vertCount
            self.vertCount += 1
            self.coordsId[end] = endID
            self.idCoords[endID] = end
            self.verts[endID] = []
            self.vertPolys[endID] = []
            self.vertList.append(end)
        
        if endID not in self.verts[startID]:    
            self.verts[startID].append(endID)
            self.verts[endID].append(startID)
            self.edList.append((start,end))
        
        self.display = True
        return [startID,endID]
    
    def addJoin(self,start,end):
        id = self.addEdge(start,end)
        if self.smart:
            self.findPolygon(id[0],id[1])

    def moveVertex(self,old,new):
        id = self.coordsId[old]
        del self.coordsId[old]
        self.coordsId[new] = id
        self.idCoords[id] = new
        self.modif = True
        self.display = True
    
    def addPolygon(self,points):
        polyID = self.polyCount
        self.polyCount += 1
        self.polyVerts[polyID] = []
        
        root = points[0]
        prev = points[-1]
        for point in points:
            id = self.addEdge(prev,point)
            self.vertPolys[id[1]].append(polyID)

            if self.coordsId[root] not in id:
                id.append(self.coordsId[root])
                self.polyVerts[polyID].append(id)
                
                poly = [self.idCoords[i] for i in id]
                norm = self.solveNorm(poly)
                self.polys.append( (poly,norm) )
            
            prev = point

        if self.smart:
            prev = self.coordsId[points[-1]]
            for point in points:
                cur = self.coordsId[point]
                self.findPolygon(prev,cur)
                prev = cur
                
    def removeVertex(self,vertex):
        if not vertex in self.coordsId:
            return
        id = self.coordsId[vertex]
        del self.idCoords[id]
        del self.coordsId[vertex]

        for neighbour in self.verts[id]:
            self.verts[neighbour].remove(id) 
        del self.verts[id]
        
        vertL = []
        for poly in self.vertPolys[id]:
            v =  self.polyVerts[poly]
            l = v[0][:]
            for i in v[1:]:
                l.append(i[1])
            vertL.append((l,poly))
            del self.polyVerts[poly]
        for rem in vertL:
            for i in rem[0]:
                if rem[1] in self.vertPolys[i]:
                    self.vertPolys[i].remove(rem[1])
        del self.vertPolys[id]

        self.modif = True
        self.display = True

    # Loops through all edges and see which edges form a closed polygon
    def findPolygon(self,key,start):
        poly = []
        # For each next vert of that vertex (end point of path)
        for end in self.verts[key]:
            size = 6
            if start != end:
                # Check if all 3 points are in an existing polygon
                flag = True
                for p in self.polyVerts:
                    v = self.polyVerts[p]
                    if v != []:
                        l = v[0][:]
                        for i in v[1:]:
                            l.append(i[1])
                        if key in l and start in l and end in l:
                            flag = False
                            break
                if flag:
                    # Create queue of possible paths
                    queue = deque([[key,start]])
                    length = 1
                    while len(queue) > 0:
                        # Get the next path
                        path = queue.popleft()
                        length = len(path)
                        # Check that path has not exceeded minimal
                        # polygon
                        if length == size:
                            break
                        node = path[-1]
                        # Create all expansions of the path
                        for next in self.verts[node]:
                            # Crossing itself
                            if next in path:
                                pass
                            # Found non-trivial path back to end vert
                            elif next == end:
                                newPath = path[:]
                                newPath.append(next)
                                poly.append(newPath)
                                break
                            # Add to set of paths
                            else:
                                newPath = path[:]
                                newPath.append(next)
                                queue.append(newPath)
        
        s = poly[:]
        for p in poly:
            e = []
            pr = p[-1]
            for cr in p:
                e.append((pr,cr))
                pr=cr
            s.remove(p)
            length = 0
            queue = deque([([e,[]],[])])
            c = True
            while (len(queue) > 0 and c):
                set = queue.popleft()
                length = len(set[1])
                if length > 3:
                    break
                for i in self.vertPolys[set[0][0][0][0]]:
                    t = [set[0][0][:],set[0][1][:]]
                    q = set[1][:]
                    v = self.polyVerts[i]
                    if v != []:
                        l = [v[0][2],v[0][0],v[0][1]]
                        for i in v[1:]:
                            l.append(i[1])
                    if len(l) > len(p) or l in q or set[0][0][0][1] not in l:
                        continue
                    u = []
                    pr = l[-1]
                    for cr in l:
                        u.append((pr,cr))
                        pr=cr
                    for j in u:
                        ji = (j[1],j[0])
                        if j in t[0]:
                            t[0].remove(j)
                            t[1].append(j)
                        elif ji in t[0]:
                            t[0].remove(ji)
                            t[1].append(ji)
                        elif j in t[1] or ji in t[1]:
                            pass
                        else:
                            t[0].append(j)
                    if t[0] == []:
                        c = False
                        break
                    q.append(l)
                    queue.append((t,q))
                for i in s:
                    t = [set[0][0][:],set[0][1][:]]
                    q = set[1][:]
                    if len(i) > len(p) or i in q:
                        continue
                    u = []
                    pr = i[-1]
                    for cr in i:
                        u.append((pr,cr))
                        pr=cr
                    for j in u:
                        ji = (j[1],j[0])
                        if j in t[0]:
                            t[0].remove(j)
                            t[1].append(j)
                        elif ji in t[0]:
                            t[0].remove(ji)
                            t[1].append(ji)
                        elif j in t[1] or ji in t[1]:
                            pass
                        else:
                            t[0].append(j)
                    if t[0] == []:
                        c = False
                        break
                    q.append(i)
                    queue.append((t,q))
            if c:
                s.append(p)

        self.smart=False
        for p in s:
            self.addPolygon([self.idCoords[i] for i in p])
        self.smart=True
    
    def polygonList(self):
        if self.modif:
            self.polys = []
            for i in self.polyVerts:
                for j in self.polyVerts[i]:
                    poly = [self.idCoords[k] for k in j]
                    norm = self.solveNorm(poly)
                    self.polys.append( (poly,norm) )
        
        return self.polys

    def vertexList(self):
        if self.modif:
            self.vertList = []
            for i in self.verts:
                self.vertList.append(self.idCoords[i])
        return self.vertList

    def edgeList(self):
        if self.modif:
            self.edList = []
            for i in self.verts:
                ci = self.idCoords[i]
                for j in self.verts[i]:
                    cj = self.idCoords[j]
                    if (cj,ci) not in self.edList:
                        self.edList.append((ci,cj))
        return self.edList
    
    def fileImport(self,file):
        loader = ModelLoader(file)
        model = loader.loadModel()
        for face in model['faces']:
            self.addPolygon([model['verts'][vert[0]-1] for vert in face])


if __name__ == "__main__":
    v = Vertices()
    v.fileImport('models/dodecahedron.obj')
    print len(v.polygonList())
    print len(v.verts)
    for i in v.polygonList():
        print [v.coordsId[j]+1 for j in i]
    """v.addPolygon([(1,),(2,),(3,)])
    print v.polygonList()
    print ''
    v.addPolygon([(5,),(6,),(7,)])
    print v.polygonList()
    print ''
    v.addEdge((1,),(5,))
    print v.polygonList()
    print ''
    v.addEdge((2,),(6,))
    print v.polygonList()
    print ''
    v.addEdge((3,),(7,))
    print v.polygonList()
    print ''
    v.removeVertex((7,))
    print v.polygonList()
    print ''"""

